package leetcode.cn;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/10/5 9:10
 * @注释:柠檬水找零
 */
public class LemonChange {
//    在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
//每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
//注意，一开始你手头没有任何零钱。
//给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
    public static void main(String[] args) {
        int[] bills = {5, 5, 5, 5, 20, 20, 5, 5, 20, 5};
        boolean b = lemonadeChange1(bills);
        System.out.println(b);
    }

    //最优解
    public static boolean lemonadeChange2(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int x : bills) {
            if (x == 5) {
                five++;
                continue;
            } else if (x == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            } else if (x == 20) {
                if (five != 0 && ten != 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else return false;
            }
        }
        return true;
    }

    //较为复杂
    public static boolean lemonadeChange1(int[] bills) {
        int[] arr = {0, 0, 0};//分别代表零钱的5,10,20
        for (int i : bills) {
            if (i == 5) {
                arr[0] += 1;
                continue;
            } else if (i == 10) {
                if (arr[0] < 1) {
                    return false;
                } else {
                    arr[0]--;
                    arr[1]++;
                }
            } else if (i == 20) {
                if (arr[1] < 1) {//先找10+5的 ---没有10元的
                    if (arr[0] < 3) {//没有5元的
                        return false;
                    } else if (arr[0] >= 3) {//有3张5元的
                        arr[0] -= 3;
                        arr[2]++;
                    }
                } else {//有>=1张10元的
                    if (arr[0] < 1) {//没有5元的
                        return false;
                    } else if (arr[0] >= 1) {
                        arr[0]--;
                        arr[1]--;
                        arr[2]++;
                    }
                }
            }
        }
        return true;
    }
}
